#pragma once

#include "maxPriorityQueue.h"
#include "myExceptions.h"
#include "changeLen1D.h"

#include <sstream>
#include <iterator>

using namespace std;

template <class T>
class maxHeap : public maxPriorityQueue<T>
{
	public:
        explicit maxHeap(int initialCapacity = 10);
        ~maxHeap() override {delete [] heap; }

        bool empty() const override { return heapSize == 0; }
        int size() const override { return heapSize; }
        const T& top() override {
            if(heapSize == 0) throw queueEmpty();
            return heap[1];
        }
        void pop() override;
        void push(const T&) override;
        void initialize(T *, int);
        void deactivateArray() { heap = nullptr;
               arrayLength = heapSize = 0;
              }
        void output(ostream& out) const;


	private:
		/* The number of elements in the queue */
		int heapSize;
		/* Queue capacity + 1*/
		int arrayLength;
		/* Element array */
		T* heap;
};

template <class T>
maxHeap<T>::maxHeap(int initialCapacity)
{
    if(initialCapacity < 1) {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Must be > 0";
        throw illegalParameterValue(s.str());
    }

    arrayLength = initialCapacity + 1;
    heap = new T[arrayLength];
    heapSize = 0;

}

template <class T>
void maxHeap<T>::push(const T& theElement)
{
    if(heapSize == arrayLength - 1) {
        changeLen1D(heap, arrayLength, arrayLength * 2);
        arrayLength *= 2;
    }

    int currentNode = ++heapSize;

    while(currentNode != 1 && heap[currentNode / 2] < theElement) {
        heap[currentNode] = heap[currentNode / 2];
        currentNode /= 2;
    }

    heap[currentNode] = theElement;
}

template <class T>
void maxHeap<T>::pop()
{
    if(heapSize == 0)
        throw queueEmpty();

    heap[1].~T();

    T lastElement = heap[heapSize--];

    int currentNode = 1, child = 2;

    while(child <= heapSize) {

        if(child < heapSize && heap[child] < heap[child + 1])
            child ++;

        if(lastElement >= heap[child])
            break;

        heap[currentNode] = heap[child];// move chile up
        currentNode = child; //move down a level
        child *= 2;
    }

    heap[currentNode] = lastElement;

}

template <class T>
void maxHeap<T>::initialize(T *theHeap, int theSize)
{
    delete [] heap;

    heap = theHeap;
    heapSize = theSize;

    /* Heapify */
    for(int root = heapSize/2; root >= 1; root--) {
        T rootElement = heap[root];
        /* Find place to put rootElement*/

        /* parent of child is target location for rootElement */
        int child = 2 * root;

        while(child <= heapSize) {
            /* heap[child] should be larger sibling */
            if(child < heapSize && heap[child] < heap[child+1])
                child ++;

            /* Can we  put rootElement in heap[child/2] ? */
            if(rootElement >= heap[child])
                break; //YES
            //NO
            /* Move child up */
            heap[child/2] = heap[child];
            /* Move down a level */
            child *= 2;
        }
        /* Put rootElement in heap[child/2] */
        heap[child/2] = rootElement;
    }
}
/**/
template<class T>
void maxHeap<T>::output(ostream& out) const
{
    copy(heap+1, heap+heapSize+1, ostream_iterator<T>(out, "  "));
}

/* Overload << */
template<class T>
ostream& operator<<(ostream& out, const maxHeap<T>& x)
{
    x.output(out);
    return out;
}

int testMaxHeap(void);
